package org.czx.datactruct.ch9_faster_sorting_methods;

/**
 * @author czx
 * @date 2020/9/25 16:08
 */
public class SortArray {
    public static <T extends Comparable<? super T>> void mergeSort(T[] a, int first, int last) {
        // The cas is safe because the new array contains null entries
        @SuppressWarnings("unchecked")
        T[] tempArray = (T[]) new Comparable<?>[a.length];
        mergeSort(a, tempArray, first, last);
    }

    // Sorts the array entries a[first...last] recursively.
    private static <T extends Comparable<? super T>> void mergeSort(T[] a, T[] tempArray, int first, int last) {
        int mid;
        if (first < last) {
            mid = first + (last - first) / 2;
            mergeSort(a, tempArray, first, mid);
            mergeSort(a, tempArray, mid + 1, last);
            if (a[mid].compareTo(a[mid + 1]) > 0)
                merge(a, tempArray, first, mid, last);
        }
    }

    // Merges the adjacent subarrays a[first...mid] and a[mid + 1...last].
    private static <T extends Comparable<? super T>> void merge(T[] a, T[] tempArray, int first, int mid, int last) {
        int beginHalf1 = first;
        int endHalf1 = mid;
        int beginHalf2 = mid + 1;
        int endHalf2 = last;

        // While both subarrays are not empty, compare an entry in one subarray with
        // an entry in teh other; then copy the smaller item into the temporary array
        int index = first; // Next available location in tempArray
        while ((beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2)) {
            if (a[beginHalf1].compareTo(a[beginHalf2]) <= 0) {
                tempArray[index] = a[beginHalf1];
                beginHalf1++;
            } else {
                tempArray[index] = a[beginHalf2];
                beginHalf2++;
            } // end if
            index++;
        } // end while
        // Assertion: One subarray has been completely copied to tempArray.

        // Copy remaining entries from other subarray to tempArray
        if (beginHalf1 > endHalf1) // remaining array is latter half
        {
            for (int i = beginHalf2; i <= endHalf2; i++) {
                tempArray[index] = a[i];
                index++;
            } // end for
        } else {
            if (beginHalf2 > endHalf2) {
                for (int i = beginHalf1; i <= endHalf1; i++) {
                    tempArray[index] = a[i];
                    index++;
                } // end for
            }
        }

        // Copy entries from tempArray to array a
        for (int i = first; i <= last; i++) {
            a[i] = tempArray[i];
        }
    }
}
